﻿//1856. 子数组最小乘积的最大值
//一个数组的 最小乘积 定义为这个数组中 最小值 乘以 数组的 和 。
//比方说，数组[3, 2, 5] （最小值是 2）的最小乘积为 2 * (3 + 2 + 5) = 2 * 10 = 20 。
//给你一个正整数数组 nums ，请你返回 nums 任意 非空子数组 的最小乘积 的 最大值 。由于答案可能很大，请你返回答案对  109 + 7 取余 的结果。
//请注意，最小乘积的最大值考虑的是取余操作 之前 的结果。题目保证最小乘积的最大值在 不取余 的情况下可以用 64 位有符号整数 保存。
//子数组 定义为一个数组的 连续 部分。


class Solution {
public:
    const int mod = 1e9 + 7;
    int maxSumMinProduct(vector<int>& nums)
    {
        long long ans = 0;
        int n = nums.size();
        vector<long long> prev(n + 1);
        prev[0] = 0;
        for (int i = 0; i < n; i++)
        {
            prev[i + 1] = prev[i] + nums[i];
        }
        nums.push_back(-1);
        stack<int> sta;
        sta.push(-1);
        for (int i = 0; i < nums.size(); i++)
        {
            while (sta.size() > 1 && nums[sta.top()] > nums[i])
            {
                int cur = nums[sta.top()];
                sta.pop();
                int left = sta.top() + 1;
                int right = i - 1;
                ans = max(ans, 1LL * cur * (prev[right + 1] - prev[left]));
            }
            sta.push(i);
        }
        return ans % mod;
    }
};